//
// Created by wdq on 22-9-21.
//
#include <iostream>
#include <cstring>

using namespace std;


void merge(int *dest, const int *left, const int *right, int leftLength, int rightLength) {
    int i = 0, j = 0, k = 0;
    while (i < leftLength || j < rightLength) {
        if (i == leftLength) {
            dest[k++] = right[j++];
        } else if (j == rightLength) {
            dest[k++] = left[i++];
        } else if (left[i] < right[j]) {
            dest[k++] = left[i++];
        } else if (left[i] >= right[i]) {
            dest[k++] = right[j++];
        }
    }
    delete[]left;
    delete[]right;


}

int *mergeSort(int nums[], int length) {
    if (length <= 1) {
        return nums;
    }
    int half = length / 2;
    int *left = new int[half];
    int *right = new int[length - half];
    memcpy(left, nums, sizeof(int) * half);
    memcpy(right, nums + half, sizeof(int) * (length - half));
    left = mergeSort(left, half);
    right = mergeSort(right, length - half);
    int *mergeResult = new int[length];
    merge(mergeResult, left, right, half, length - half);
    return mergeResult;

}


int main() {

    int nums[] = {2, 6, 1, 56, 25, 67, 89, 5, 3, 3, 4};
    printf("nums: ");
    for (auto &i: nums) {
        printf("%-4d ", i);
    }
    printf("\n");
    int *p = mergeSort(nums, sizeof(nums) / sizeof(int));
    printf("sorting..........................\n");
    printf("nums: ");
    for (int i = 0; i < sizeof(nums) / sizeof(int); i++) {
        printf("%-4d ", *(p + i));
    }
    printf("\n");
    return 0;
}